#ifndef GX_POOL_HPP
#define GX_POOL_HPP

#include "Basic/Array.hpp"
#include "Basic/Link.hpp"

namespace GxLibBasic
{
	template <typename _Type, int BlockSize>
	class PoolBlock
	{
	public:
		int Count;
		bool Flag[BlockSize];
		_Type Items[BlockSize];
	public:
		PoolBlock()
		{
			Count = 0;
			memset(Flag,0,BlockSize);
		}
		//int FindUnused()
		//{
		//	if (Count == BlockSize)
		//		return -1;
		//	for (int i=0; i<BlockSize; i++)
		//		if (Flag[i] == false)
		//			return i;
		//	return -1;
		//};
	};

	template <typename _Type, int BlockSize>
	class Pool
	{
	private:
		class gxResID
		{
		public:
			int BlockID;
			int ID;
			gxResID()
			{
			}
			gxResID(int bid, int id)
				:BlockID(bid), ID(id)
			{
			}
			bool operator ==(const gxResID & r)
			{
				return (BlockID == r.BlockID && ID == r.ID);
			}
			bool operator>(const gxResID & r)
			{
				return (BlockID > r.BlockID || (BlockID == r.BlockID && ID > r.ID));
			}
			bool operator<(const gxResID & r)
			{
				return (BlockID < r.BlockID || (BlockID == r.BlockID && ID < r.ID));
			}
		};
		int FCurBlock, FCurID;
		typedef typename Link<PoolBlock<_Type,BlockSize> >::LinkNode gxPoolNode;
		typedef typename Link<gxResID>::LinkNode gxResIDNode;
		gxPoolNode * FCurNode;
		Link<PoolBlock<_Type,BlockSize> > FPool;
		Link<gxResID> UnusedID;
		Array<gxResID> UsedID;
	public:
		Pool()
		{
			FCurBlock = FCurID = 0;
		}
		~Pool()
		{}
	public:
		_Type * Alloc()
		{
			/*
			if (!FPool.Count())
				FPool.Append();
			for (Link<PoolBlock<_Type,BlockSize> >::LinkNode* i = FPool.Begin();i; i= i->GetNext())
			{
				int rs = i->Data.FindUnused();
				if (rs!=-1)
				{
					i->Data.Flag[rs] = true;
					i->Data.Count ++;
					return &(i->Data.Items[rs]);
				}
			}
			FPool.Append();
			FPool.End()->Data.Flag[0] = true;
			FPool.End()->Data.Count = 1;
			return &FPool.End()->Data.Items[0];
			*/
			return GetObject(AllocHandle());
		}
		void AppendPool()
		{
			FPool.Append();
			for (int i=0; i<BlockSize; i++)
			{
				gxResIDNode * n = UnusedID.Append();
				n->Data.BlockID = FPool.Count()-1;
				n->Data.ID = i;
			}
		}
		Int AllocHandle()
		{
			if (!UnusedID.Count())
			{
				AppendPool();
			}
			int bid = UnusedID[0].BlockID;
			int id = UnusedID[0].ID;
			FPool[bid].Count++;
			FPool[bid].Flag[id] = true;
			int rs = bid*BlockSize + id;
			
			UsedID.Add(UnusedID[0]);
			UnusedID.Begin()->Delete();
			return rs;
		}

		_Type * GetObject(Int handle)
		{
			int i,j;
			if (handle < 0 || handle > FPool.Count()*BlockSize)
				return 0;
			i = handle / BlockSize;
			j = handle % BlockSize;
			if (i>=0 && FPool.Count()>i)
				return &FPool[i].Items[j];
			else
				return 0;
		}

		Int GetHandle(_Type * ptr)
		{
			int icount = 0;
			for (gxPoolNode* i = FPool.Begin();i; i= i->GetNext(),icount++)
			{
				if (ptr>= i->Data.Items && ptr <= i->Data.Items+BlockSize-1)
				{
					int id = ptr-i->Data.Items;
					return icount*BlockSize + id;
				}
			}
			return -1;
		}

		Int Capacity()
		{
			return FPool.Count() * BlockSize;
		}

		

		bool IsUsed(_Type * ptr)
		{
			for (gxPoolNode* i = FPool.Begin();i; i= i->GetNext())
			{
				if (ptr>= i->Data.Items && ptr <= i->Data.Items+BlockSize-1)
				{
					int id = ptr-i->Data.Items;
					/*for (gxResIDNode *n = UnusedID.Begin();n;n=n->GetNext())
					{
						if (n->Data.BlockID == i-FPool.Begin() && n->Data.ID == id)
							return true;
					}*/
					return i->Data.Flags[id];
				}
			}
			return false;
		}

		void Free(_Type * ptr)
		{
	#ifdef _DEBUG
			//for (gxPoolNode* i = FPool.Begin();i; i= i->GetNext())
			//{
			//	if (ptr>= i->Data.Items && ptr <= i->Data.Items+BlockSize-1)
			//	{
			//		
			//		int id = ptr-i->Data.Items;
			//		
			//		for (gxResIDNode *n = UnusedID.Begin();n;n=n->GetNext())
			//		{
			//			if (n->Data.BlockID == i-FPool.Begin() && n->Data.ID == id)
			//				throw "An object has been freed twice.";
			//		}
			//		break;
			//	}
			//}
	#endif
			int num = 0;
			for (gxPoolNode* i = FPool.Begin();i; i= i->GetNext())
			{
				if (ptr>= i->Data.Items && ptr <= i->Data.Items+BlockSize-1)
				{
					int id = ptr-i->Data.Items;
					if (i->Data.Flag[id])
					{
						i->Data.Flag[id] = false;
						gxResIDNode * n = UnusedID.Append();
						n->Data.BlockID = num;
						n->Data.ID = id;
						i->Data.Count--;
						gxResID res;
						res.BlockID = num;
						res.ID = id;
						int fid = UsedID.Find(res);
						if (fid != -1)
							UsedID.Delete(fid);
					}

					return;
				}
				num ++;
			}
			throw Exception(String(L"Pool.Free: Cannot locate specified data pointer."),0);
		}

		_Type * MoveFirst()
		{
			FCurBlock = FCurID = 0;
			FCurNode = FPool.Begin();
			if (UsedID.Count())
			{
				while (FCurBlock < UsedID[0].BlockID)
				{
					FCurBlock ++;
					FCurNode = FCurNode->GetNext();
				}
				return &(FCurNode->Data.Items[UsedID[0].ID]);
			}
			else
				return 0;
		}
		/*_Type * CompleteMoveFirst()
		{
			return MoveFirst();
		}
		_Type * CompleteMoveNext()
		{
			FCurID ++;
			if (FCurID == BlockSize)
			{
				FCurID = 0;
				FCurNode = FCurNode->GetNext();
				FCurBlock ++;
			}

			if (FCurBlock >= FPool.Count())
				return 0;
			else
				return &(FCurNode->Data.Items[FCurID]);
		}*/
		_Type * MoveNext()
		{
			//do
			//{
			//	FCurID ++;
			//	if (FCurID == BlockSize)
			//	{
			//		FCurID = 0;
			//		FCurNode = FCurNode->GetNext();
			//		FCurBlock ++;
			//	}

			//	if (FCurBlock >= FPool.Count())
			//		return 0;
			//}while(!FCurNode->Data.Flag[FCurID]);
			//return &(FCurNode->Data.Items[FCurID]);
			FCurID ++;
			if (UsedID.Count() > FCurID)
			{
				if (FCurBlock > UsedID[FCurID].BlockID)
				{
					while (FCurBlock > UsedID[FCurID].BlockID)
					{
						FCurBlock --;
						FCurNode = FCurNode->GetPrevious();
					}
				}
				else
				{
					while (FCurBlock < UsedID[FCurID].BlockID)
					{
						FCurBlock ++;
						FCurNode = FCurNode->GetNext();
					}
				}
				return &(FCurNode->Data.Items[UsedID[FCurID].ID]);
			}
			return 0;
		}

		void FreeCurrent()
		{
			int id = UsedID[FCurID].ID;
			int num = UsedID[FCurID].BlockID;
			if (FCurNode->Data.Flag[id])
			{
				FCurNode->Data.Flag[id] = false;
				gxResIDNode * n = UnusedID.Append();
				n->Data.BlockID = num;
				n->Data.ID = id;
				FCurNode->Data.Count--;
				gxResID res;
				res.BlockID = num;
				res.ID = id;
				UsedID.Delete(FCurID);
				FCurID --;
			}
		}

		/*_Type * MovePrevious()
		{
			FCurID --;
			if (FCurID == -1)
			{
				FCurBlock --;
				FCurNode = FCurNode->GetPrevious();
				FCurID = BlockSize -1;
			}
			if (FCurBlock<0)
				return 0;
			if (FCurBlock >= FPool.Count())
				return 0;
			
			return &(FCurNode->Data.Items[FCurID]);
		}

		_Type * MoveLast()
		{
			FCurID = BlockSize -1;
			FCurNode = FPool.End();
			FCurBlock = FPool.Count();
			if (FCurBlock<0)
				return 0;
			if (FCurBlock >= FPool.Count())
				return 0;
			return &(FCurNode->Data.Items[FCurID]);
		}*/

		int Count()
		{
			int rs = 0;
			for (gxPoolNode * i = FPool.Begin(); i; i=i->GetNext())
				rs += i->Data.Count;
			return rs;
		}
	};
}
#endif